/*
	最大子段和：
	f[i] = f[i - 1]>0 ? nums[i] + f[i] : nums[i]
*/

int maxSubArray1(int *a, int n)
{
	int sum = 0, pre = 0;;

	for(int i = 0; i <= n-1; i++)
	{
		if (pre > 0)
			pre = pre + a[i];
		else
			pre = a[i];

		if (pre > sum)
			sum = pre;
	}

	return sum;
}

/*
	最大子矩阵之和
	时间O(m^2 * n)
	空间O()
*/

int maxSubMatrix(int m, int n, int **a)
{
	int b[n+1],sum = 0;
/*	for (int i = 1; i <= n; i++)
	{
		b[i] = 0;
	}//一维数组初始化为0
*/
	for (int i = 1; i <= m; i++)//假设最大的子矩阵一定包括i行
	{
		for (int k = 1; k <= n; k++)
		{
			b[k] = 0;
		}

		for (int j = i; j <= n; j++)//将第i行与 (i行 + i+1行)、 (i行 + i+1行 + i+2行) 之和....依次比较
		{
			for (int k = 1; k <= n ; k++)
			{
				b[k] += a[j][k];//两行相加后 进行 子数列比较
			}

			int max = maxSubArray(b,n);

			if (max > sum)
				sum = max;
		}

	}//for_1
}


/*
	最大子段和分支思想:
	a[1...n]与a[1...n/2]最大子段和相等
	a[1...n]与a[n/2+1...n]最大子段和相等
	a[1...n]与a[1...n/2]最大子段和 和 a[n/2+1...n]最大子段和 的和相等
*/

int maxSubArray2(int *a, int left, int right)
{
	int sum = 0;
	if(left == right)
		sum = a[left]>0?a[left]:0;
	else
	{
		int center = (left+right)/2;
		int leftsum = maxSubArray2(a, left, center);
		int rightsum = maxSubArray2(a, center+1, right);

		int s1 = 0;
		int lefts = 0;
		for(int i = center; i>= left; i--)
		{
			lefts = lefts+a[i];
			if(lefts > s1)
				s1 = lefts;
		}

		int s2 = 0;
		int rights = 0;
		for(int i = center+1; i<= right; i++)
		{
			rights = rights+a[i];
			if(rights > s2)
				s2 = rights;
		}

		sum = s1+s2;
		if(sum < leftsum)
			sum = leftsum;
		if(sum < rightsum)
			sum = rightsum;
	}

	return sum;
}
//记录位置的最大子段和
int maxSubArray3(int *a, int n, int *b)
{
	b[0] = a[0];
	int max = b[0];

	for(int i = 1; i < n; i++)
	{
		if(b[i-1] > 0)
			b[i] = b[i-1]+a[i];
		else
			b[i] = a[i];

		if(b[i] > max)
			max = b[i];
	}

	return max;
}

//最大M字段和
int maxMSum(int m, int n, int *a)
{//b[i][j] j作为最后一项 分为i子段的最大值
	int b[m+1][n+1];

	for(int i = 0; i<=m; i++)
	{
		b[i][0] = 0;
	}
	for(int i = 0; i<=n; i++)
	{
		b[0][i] = 0;
	}

	for(int i = 1; i<=m; i++)
	{
		for(int j = i; j<=i+n-m; j++)
		{
			if(j>i)
			{
				b[i][j] = b[i][j-1]+a[j];

				for(int k = i-1; k<j; k++)
				{
					if(b[i][j] < b[i-1][k]+a[j])
						b[i][j] = b[i-1][k] + a[j];
				}
			}
			else
				b[i][j] = b[i-1][j-1]+a[j];
		}
	}

	int sum = 0;
	for(int i = m; i<=n; i++)
	{
		if(sum < b[m][i])
			sum = b[m][i];
	}

	return sum;
}

int main(void)
{

	int a[6] = {-2,11,-4,13,-5,-2};
	int result;
	result = maxSubArray(a,6);
	printf("结果是%d\n",result);
}